import random
from typing import *
from bisect import bisect_left


class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n, m = len(skill), len(mana)
        d = [0] * (n + 1)
        totmx = 0

        def max(a, b):
            return a if a >= b else b

        for i in range(m):
            d[0] = d[1]
            mx = 0
            for j in range(n + 1):
                if j > 0:
                    d[j] = d[j - 1] + skill[j - 1] * mana[i]
                if j < n:
                    mx = max(mx, d[j + 1] - d[j])
            totmx += mx
        return d[-1] + totmx


s = Solution()
print(s.minTime(skill=[1, 5, 2, 4], mana=[5, 1, 4, 2]))
print(s.minTime(skill=[1, 1, 1], mana=[1, 1, 1]))


# [15, 29, 15, 25, 18, 21, 49, 23, 22, 45]
# [11, 22, 31, 10, 43, 16, 26, 28, 4, 18]
# [2778, 709, 1572, 1926, 2237, 1337, 4451, 1002, 1528, 3512]
# [4441, 4229, 277, 1637, 3423, 2318, 3147, 1851, 1887, 2415]
# class Solution:
#     def minTime(self, skill: List[int], mana: List[int]) -> int:
#         n, m = len(skill), len(mana)
#         dp = [0] * (n + 1)
#         for i in range(1, n + 1):
#             dp[i] = dp[i - 1] + skill[i - 1] * mana[0]

#         def f(s, j):
#             for i in range(n - 1):
#                 s = s + skill[i] * mana[j]
#                 if s < dp[i + 2]:
#                     return False
#             return True

#         for j in range(1, m):
#             k = bisect_left(range(dp[1], dp[-1] + 1), True, key=lambda a: f(a, j))
#             dp[0] = dp[1] + k
#             for i in range(1, n + 1):
#                 dp[i] = dp[i - 1] + skill[i - 1] * mana[j]

#         return dp[-1]


class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n, m = len(skill), len(mana)
        dp = [[0] * (n + 1) for _ in range(m)]
        for i in range(m):
            if i > 0:
                dp[i][0] = dp[i - 1][1]
            for j in range(1, n + 1):
                dp[i][j] = dp[i][j - 1] + skill[j - 1] * mana[i]
            if i > 0:
                mx = 0
                for j in range(n):
                    mx = max(mx, dp[i - 1][j + 1] - dp[i][j])
                for j in range(n + 1):
                    dp[i][j] += mx
        return dp[-1][-1]


[1, 5, 2, 4]
[5, 1, 4, 2]
[1, 1, 1]
[1, 1, 1]
[1, 2, 3, 4]
[1, 2]
[15, 29, 15, 25, 18, 21, 49, 23, 22, 45]
[11, 22, 31, 10, 43, 16, 26, 28, 4, 18]
[2778, 709, 1572, 1926, 2237, 1337, 4451, 1002, 1528, 3512]
[4441, 4229, 277, 1637, 3423, 2318, 3147, 1851, 1887, 2415]
[299, 415, 596, 618, 565]
[185, 644, 407, 366, 230]

a = 65000
print(65000 * 0.0175 * 3)
print(55000 * 0.0175 * 3)
print(1.5 * 13200)
